package com.example.leetcode.sort;

import java.util.Arrays;

/**
 * @ClassName 插入排序
 *  思路：将数组分成一个有序数组和一个无序数组，开始时有序数组只有一个元素，无序数组有n-1个元素
 *  每次排序从无序数组中取出第一个元素，将它一次和有序数组的元素进行比较，将它插入到有序数组中合适
 *  的位置，使之成为新的有序数组
 *
 *
 *
 * @Description TODO
 * @Author liuzhihui
 * @Date 19/4/2021 下午 11:31
 * @Version 1.0
 **/
public class InsertSort {

    public static void main(String[] args) {
        int arr[]={3, 9, -1, 10, -2};
        System.out.println("排序前：" + Arrays.toString(arr));
        sort2(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    private static void sort(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            //待插入的数
            int tempValue = nums[i];
            //待插入的数的前一个元素的下标
            int tempIndex = i -1;

            // 如果待插入的数小于前面的元素
            while(tempIndex >= 0 && tempValue < nums[tempIndex]){
                //那么前面的向后移动，前面留出位置，给待插入的元素
                nums[tempIndex + 1] = nums[tempIndex];
                //指针前移，继续找比待插入元素大的元素
                tempIndex--;
            }
            //终于找到了小于等于待插入的元素
            //小于它的数的后一个位置给待插入的数,tempIndex + 1已经是空位了
            nums[tempIndex + 1] = tempValue;
        }
    }

    private static void sort1(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            //待插入的元素
            int tempValue = nums[i];
            //待插入的元素的前一个元素
            int tempIndex = i - 1;

            while(tempIndex >= 0 && tempValue <nums[tempIndex]){
                nums[tempIndex + 1] = nums[tempIndex];
                tempIndex--;
            }
            nums[tempIndex + 1] = tempValue;
        }
    }

    private static void sort2(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            // 待插入的元素
            int preValue = nums[i];
            //待插入的元素的前驱元素
            int preIndex = i - 1;
            // 将待插入的元素和前驱元素依次比较，直到找到合适的位置
            while(preIndex >= 0 && nums[preIndex] > preValue){
                //todo 这里注意，经常忘记
                nums[preIndex + 1] = nums[preIndex];
                preIndex--;
            }
            nums[preIndex + 1] = preValue;
        }
    }

}
